package setOfCollectionDemo.treeDemo;

import java.util.Comparator;
import java.util.TreeSet;

/*
二叉树:每一个节点最多只有两个子节点,乱序存放,查找慢
二叉搜索树:二叉树中的数据按序排列,左子节点小于根节,右子节点大于根节点,某些情况可能出现瘸子树(只有一侧有分支)
平衡二叉树:任意一个节点,左右子树的高度相差小于等于1
        旋转:添加元素时,可能出现不平衡的情况,通过旋转,使树平衡.
        左旋:右子树出现不平衡,从添加元素位置向根节点查找,找到不平衡的支点,
            将支点的右子节点提升为父节点,支点下降为左子节点,原先右子节点的左子节点变成支点下降后左子节点的右子节点
        左左:左子节点的左子树,添加元素,一次右旋可以平衡
        左右:左子节点的右子树,添加元素,先局部(支点左子节点)左旋,再以支点整体右旋
        右右:右子节点的右子树,添加元素,一次左旋可以平衡
        右左:右子节点的左子树,添加元素,先局部(支点的右子节点)右旋,再以支点整体左旋
红黑树:根据红黑规则定义的不高度平衡二叉树
      红黑规则:1.根节点必须为黑色
          2.一个节点没有父节点或子节点,为他添加叶子节点Nil,叶子节点视为黑色
          3.不能出现两个红石节点相连
          4.任意节点到左右子树的最短路径相等
          5.默认添加的节点颜色为红石(红石效率比黑色高)
      添加节点的规则:
          是根节点:变黑色
          非根节点{ 1.父节点为黑色:不需要操作
                   2.父节点为红色{1.叔叔 为红色:将父节点与叔节点一起变黑色,再把祖父节点变红色,若祖父节点是根节点,变回黑色,若不是根节点,对祖父节点进行判断
                                2.叔叔为黑色{是根节点左子树  {当前节点是父节点的右孩子:把父节点当支点左旋,变成左左情况
                                                         当前节点是父节点的左孩子:把父节点变黑,祖父节点变红,把祖父作为支点,右旋
                                           是根节点右子树 {当前节点是父节点的左孩子:把父节点当支点右旋,变成右右
                                                         当前节点是父节点的右孩子:把父节点变黑,祖父节点变红,把祖父作为支点,左旋
                                      }}}}


TreeSet集合:存取无序,无索引,无重复,采用红黑树实现存取,去重复是通过重写比较方法实现的
            os:如果CompareTo()return 1;则可以存重复的
            1.存:调用对象的类中的CompareTo(),根据返回值,确定存放位置
                正数:存放右边 负数:存放左边 0:不存
            2.取:访问树时,从根节点开始左中右访问数据
            3.排序方式:
                    1.自然排序:实现comparable接口,重写了CompareTo()
                    2.比较器排序:实现compartor接口,重写compare(),常用匿名内部类形式重写
                  os:比较器与自然排序同时存在,优先使用比较器排序

 */
public class TreeDemo {
    public static void main(String[] args) {
        method3();
    }
        //3.2比较器排序
    private static void method3() {
        TreeSet<Student>treeSet=new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getName().compareTo(o2.getName());
            }
        });
        treeSet.add(new Student("李四",24));
        treeSet.add(new Student("赵六",23));
        treeSet.add(new Student("王五",22));
        treeSet.add(new Student("张三",23));
        System.out.println(treeSet);
    }

    //3.1自然排序
    private static void method2() {
        TreeSet<Student>treeSet=new TreeSet<>();
        treeSet.add(new Student("张三",23));
        treeSet.add(new Student("李四",24));
        treeSet.add(new Student("王五",22));
        System.out.println(treeSet);
    }

    //1.String类实现comparable接口,重写了CompareTo(),字符串可以把通过该方法排序
    private static void method1() {
        TreeSet<String>strings=new TreeSet<>();
        strings.add("232");
        strings.add("132");
        strings.add("332");
        strings.add("132");
        System.out.println(strings);
    }
}
